package LeetCode.SlideWindow;

import java.util.*;

/**
 * @author : LdLtd
 * @Date : 2023/7/24
 * @Description:438. 找到字符串中所有字母异位词
 */
public class find_all_anagrams_in_a_string {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "1234521", p = "12";
        System.out.println(solution.findAnagrams1(s, p));
    }

    static class Solution {
        /*超时*/
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            //计算匹配串排序后的hashcode
            char[] chars = p.toCharArray();
            Arrays.sort(chars);
            int code = Arrays.toString(chars).hashCode();

            Set<Character> set = new HashSet<>();
            for (char ch : chars) {
                set.add(ch);
            }

            for (int i = 0, k = 0; i < s.length()-p.length()+1; ) {
                //如果这个字母在set中
                k=i;
                while (set.contains(s.charAt(k))) {
                    //如果匹配长度完全
                    if (k-i+1 == p.length()) {
                        //如果code 相等保存答案
                        char[] subchar = s.substring(i, k+1).toCharArray();
                        Arrays.sort(subchar);
                        if (code == Arrays.toString(subchar).hashCode()) {
                            //保存答案
                            res.add(i);
                        }
                        //因为每一位都在set中，所以进一位,同时更新k的值
                        ++i;
                        break;
                        //没匹配完就继续匹配下一位
                    } else {
                        k++;
                    }
                }
                //防止跳出while循环时，hash不匹配的情况也加k
                if(!set.contains(s.charAt(k))){
                    //不包含的情况下，则调到k的下一位
                    i = k + 1;
                }

            }

            return res;
        }
        /*滑动窗口 利用Arrays.equals
        * 时间复杂度：O(m+(n−m)×Σ)，其中 nn 为字符串 ss 的长度，mm 为字符串 pp 的长度，
        * Σ 为所有可能的字符数。
        空间复杂度：O(Σ)。用于存储字符串 pp 和滑动窗口中每种字母的数量
*/
        public List<Integer> findAnagrams2(String s, String p) {
            int slen = s.length();
            int plen = p.length();
            if(plen<slen) {
                return  new ArrayList<Integer>();
            }
            List<Integer> res = new ArrayList<Integer>();
            int[] sCount = new int[26];
            int[] pCount = new int[26];
            //先初始化
            for (int i = 0; i < plen; i++) {
                ++sCount[s.charAt(i)-'a'];
                ++pCount[p.charAt(i)-'a'];
            }
            if (Arrays.equals(sCount, pCount)) {
                res.add(0);
            }

            for (int i = 0; i < slen - plen; ++i) {
                --sCount[s.charAt(i) - 'a'];
                ++sCount[s.charAt(i + plen) - 'a'];

                if (Arrays.equals(sCount, pCount)) {
                    res.add(i + 1);
                }
            }
            return res;
        }
            /*
            * 滑动窗口优化
            * 用差值来代表是否还能继续前进当不能前进时*/
        public List<Integer> findAnagrams1(String s, String p) {
                int [] c=new int[128];
                //先初始化数组，把匹配串对应的字母标记次数
                for(char ch:p.toCharArray()) c[ch]++;
                int l=0,r=0;
                List<Integer> res = new ArrayList<>();
                while(r<s.length()){
                    //如果当前位置存在于匹配串种，消耗掉当前的位置，然后右边的位置往前
                    if(c[s.charAt(r)]>0){
                        c[s.charAt(r++)]--;
                        //如果消耗到匹配的长度，就记录
                        if(r-l==p.length()) res.add(l);
                        //如果不匹配，说明右移左边界，复位计数器，直到条件再次满足
                        //p种的资源相当于存粮，r没有见到存粮时，l会补给，补给后，r会立即消耗往前走
                        //如果r遇见是存粮x中的子集x1中的一部分，后面r没有遇见存粮就不动了，l会立即补给x1个
                        //即l只会比r快一步，最大可能慢x步

                        // 找完一次异位词，其实就正好将count数组中的频次全部消耗为0
                        // 此时右指针来到一个非p字符，或者虽然是p字符但count中已经没有频次可消耗了，于是赖着不走了
                        // 左指针出动，开始为count数组作补给，
                        // 对于非p字符，左指针补一口，右指针就吃一口，亦步亦趋，直到再次遇到p中字符，右指针才可能反超，
                        // 注意，此时右指针消耗的频次，其实来自于左指针从前一个异位词那里补充的
                    }else {
                        //非匹配的串，消耗一个存一个，匹配的字符，消耗完一次会马上补充
                        c[s.charAt(l++)]++;
                    }
                }
                return  res;
        }
    }
}
